This invention relates generally to three-dimensional (3D) models, and more particularly to representing the models as triangle meshes.
As computers become increasingly more powerful, they have been increasingly used to run computer programs that utilize three-dimensional (3D) models, or objects. Such programs include game programs where a game player views his or her surroundings in three dimensions, computer-aided-drafting (CAD) programs allowing architects, engineers and designers to construct plans for real-world objects in three dimensions, as well as other programs. The three-dimensional objects used by these and other computer programs have generally become increasingly complex.
One manner by which three-dimensional models are represented within a computer is known as a triangle mesh. A triangle mesh includes a number of differently sized triangles, such that at least one edge of each triangle within the mesh is shared with another triangle, and each vertex of each triangle within the mesh is shared with at least one another triangle. Complex three-dimensional objects can be constructed utilizing triangle meshes. For example, small numbers of triangles can be used for flat surfaces of an object, while large numbers can be used to mold curved surfaces of the object, similar to the way a geodesic dome is constructed.
As triangle meshes have gained popularity to represent three-dimensional models within computers, and as these triangle meshes have become more complex to represent increasingly complex three-dimensional models, the issue of compressing the triangle mesh has become important. Compressing the triangle mesh is important to save the triangle mesh to a file for storage on a storage device such as a hard disk drive, for instance, or for sending to another computer over a network such as the Internet, for example. For these and other reasons, there is a need for the present invention.
Embodiments of the present invention relate to triangle mesh compression. In one embodiment, a method first generates a dual graph from a triangle mesh. The method then generates a binary tree structure from the dual graph.